package com.leo.basic.chapter05;

/**
 *
 * @author xuexiaolei
 * @version 2017年12月08日
 */
public class DivideAndConquer002 {
    public void merge(int[] l, int start, int mid, int end){
        int[] t = new int[end-start+1];
        int i=start,j=mid+1,k=0;
        while (i<=mid && j<=end){
            if (l[i] < l[j]){
                t[k++] = l[i++];
            }else {
                t[k++] = l[j++];
            }
        }
        while (i<=mid) t[k++] = l[i++];
        while (j<=end) t[k++] = l[j++];
        for (int m = 0; m < t.length; m++) {
            l[start+m] = t[m];
        }
    }
    public void mergeSort(int[] l, int start, int end){
        if (start < end){
            int mid = (start+end)/2;
            mergeSort(l, start, mid);
            mergeSort(l, mid+1, end);
            merge(l, start, mid, end);
        }
    }


    public int partition(int[] l, int start, int end){
        int tmp = l[start];
        int i=start,j=end;
        while (i<j){
            while (i<j && l[j]>=tmp) j--;
            l[i]=l[j];
            while (i<j && l[i]<=tmp) i++;
            l[j]=l[i];
        }
        l[i]=tmp;
        return i;
    }

    public void quickSort(int[] l, int start, int end){
        if (start < end){
            int pos = partition(l, start, end);
            quickSort(l, start, pos-1);
            quickSort(l, pos+1, end);
        }
    }
}
